package com.bigshen.algorithm.dBinarySearch.solution02SearchSortedArray;

/**
 * 33. Search in Rotated Sorted Array
 * You are given an integer array nums sorted in ascending order, and an integer target.
 *
 * Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
 *
 * If target is found in the array return its index, otherwise, return -1.
 *
 * Example 1:
 *
 * Input: nums = [4,5,6,7,0,1,2], target = 0
 * Output: 4
 * Example 2:
 *
 * Input: nums = [4,5,6,7,0,1,2], target = 3
 * Output: -1
 * Example 3:
 *
 * Input: nums = [1], target = 0
 * Output: -1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    // 一个完整的上升区间分裂为左右两个上升区间
    // 左侧为值较大的上升区间、右侧为值较小的上升区间
    // 二分法取中位值，中位值可能会落在左侧大区间，也可能是右侧小区间
    // a. 当中位值位于左侧大区间 (mid > start)
    // 当target比中位值小且比头部大，落在左侧大区间的左部，尾部左移，继续二分
    // 否则 target落在左侧大区间右部，头部右移，继续二分
    // b. 当中位值位于右侧小区间 (mid < start)
    // 当target比中位值大且比尾部小，位于右侧小区间的右部，头部右移，继续二分
    // 否则 target落在右侧小区间的左部，尾部左移，继续二分
    public int search(int[] nums, int target) {

        if (null == nums || nums.length == 0) {
            return -1;
        }

        int start = 0;
        int end = nums.length - 1;

        while(start + 1 < end) {
            int mid = start + (end-start)/2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > nums[start]) {
                // 左侧大区间
                if (nums[start] <= target && target <= nums[mid]) {
                    // target位于左侧大区间左部，尾部左移  <-- end
                    end = mid;
                } else {
                    // 位于左侧大区间右部，头部右移 start -->
                    start = mid;
                }
            } else {
                // 右侧小区间
                if (nums[mid] <= target && target <= nums[end]) {
                    // target位于右侧小区间右部，头部邮寄 start -->
                    start = mid;
                } else {
                    // target位于右侧小区间左部，尾部左移 <-- end
                    end = mid;
                }
            }
        }

        if (nums[start] == target) {
            return start;
        }

        if (nums[end] == target) {
            return end;
        }

        return -1;

    }

}
